1. Field of the Invention
The present invention relates to a Viterbi decoding circuit and a wireless device.
2. Description of the Related Art
In wireless communication, transmission data is sometimes damaged by disturbances that occur during transmission, thereby causing an error in the data. Therefore, a transmitting-end performs error correction coding on data and transmits the encoded data, and a receiving-end corrects the errors in the received data. A Viterbi decoding circuit is used to perform error correction at a receiving-end. A software wireless device processes a wireless processing, which has conventionally been actualized by hardware, by overwriting software of a hardware component. The Viterbi decoding circuit is one of the main component circuits in the wireless device.
A convolutional encoder is a widely-used error correction encoder. The convolutional encoder is uniquely represented by three types of parameters: (1) a code rate; (2) a constraint length; and (3) generator polynomials. The three parameters are determined for each wireless technology, such as a wireless local area network (LAN) and at third-generation mobile phone.
FIG. 1 is a schematic of the convolutional encoder. To avoid complicated explanations, in this example, the code rate is ½, the constraint length is 3, and the generator polynomials G0 and G1 are 111 (binary) and 101 (binary), respectively. The convolutional encoder with a constraint length of 3 is not implemented in practice.
The code rate ½in the parameters means that the convolutional encoder has one input and two outputs, as shown in FIG. 1. There are two pieces of output information, an output A and an output B, to one piece of input information, and thus, the input information is made redundant (robust) by two. The constraint length 3 indicates that the convolutional encoder has a total of three nodes, N1, N2, and N3: one input and two flip-flops (FF) 1 and 2. Four data combinations can be held by the two flip-flops 1 and 2: 0 and 0; 0 and 1; 1 and 0; and 1 and 1. Thus, the constraint length 3 can also be expressed as four states.
The generator polynomials G0 and G1 indicate combinations of exclusive OR (EOR) of each node. G0 is the generator polynomial of the output A, and G1 is the generator polynomial of the output B. In the output A, an EOR gate 3 calculates the EOR of three values: the flip-flop 2 in a back row, the flip-flop 1 in a front row, and the input. Thus, the generator polynomial G0 of the output A is 111 (binary). In the output B, an EOR gate 4 calculates the EOR of two values: the flip-flop 1 in the front row and the input. Thus, the generator polynomial G0 of the output A is 101 (binary).
Therefore, in the convolutional encoder shown in FIG. 1, the output is determined by a current input data and the input data of two cycles prior to the current input data. The values held by the flip-flops 1 and 2, namely the internal states of the flip-flops 1 and 2, change due to changes in data sequences input into the convolutional encoder. Thus, the data sequences of the output A and the output B are determined.
The Viterbi decoding circuit estimates the most probable input data input into the encoder, based on the encoder state and the output data sequence. In the state after a wireless terminal at the transmitting-end is reset and before data is transmitted (time 0), the two flip-flops 1 and 2 of the convolutional encoder are both set to 0. If this state is defined as state 0, the state of the encoder after one cycle is determined according to whether the input data input into the encoder is 0 or 1.
When the input data is 0, state 0 transitions to state 0. If the combination of value a of the output A and value b of the output B, is indicated as {a, b}, {output A, output B}={0, 0}.
Generally, the relationship between the state transition and the output in the convolution encoder shown in FIG. 1 such as that shown in the state transition shown in FIG. 2. As shown in FIG. 2, the convolution encoder shown in FIG. 1 transitions the states of the two flip-flops 1 and 2 while outputting the output A and the output B, whenever data is input. The state transition is expressed in time series as in the trellis diagram shown in FIG. 3. Although only the state transition between time 0 and time 1 is shown in FIG. 3, the topology is the same for state transitions following time 1.
As shown in FIG. 3, the state changes to state 0 at time 1 when either a transition from state 0 at time 0 (upper branch) or a transition from state 1 at time 0 (lower branch) is made. Therefore, in the Viterbi decoding circuit at the receiving-end, if the state at time 1 is state 0, the state is expected to be state 0 at time 0 and the reception signal, namely the output signal from the wireless terminal at the transmitting-end, {0, 0}, or the state is expected to be state 1 at time 0 and the output signal from the transmitting-end, {1, 1}.
The Viterbi decoding circuit calculates the distance between the two expected values (hereinafter, “Data A candidate” and “Data B candidate”) and the actual reception signals (hereinafter, “Data A” and “Data B”), namely a branch metric, according to Equation 1.Branch metric=|Data A=Data A candidate|+|Data B=Data B candidate|  (1)
The Viterbi decoding circuit assigns the smaller of the upper branch metric obtained from the upper branch and the lower branch metric obtained from the lower branch to a path metric as a surviving branch. The surviving branch is similarly determined for time 2 and later, and the surviving branches are added to the path metric. Ultimately, [number of reception data×4 states] surviving branches and four path metrics are acquired.
The path metric is equivalent to the total distance (evaluation coefficient) of a trellis path. Based on the path metric, if the trellis path is traced back in the order opposite of the receiving order, the most probable transmission data sequence with the least amount of errors can be estimated. FIG. 4 is a block diagram of a conventional Viterbi decoding circuit that performs maximum likelihood estimation. A branch metric calculating unit 5 calculates the branch metric. An add-compare-select (ACS) unit 6 determines the path metric. A path memory unit 7 holds the surviving branch. A trace back unit 8 reads the surviving branch held in the path memory unit 7, traces back the trellis path, and decodes the transmission data sequence.
The inventors of the present invention previously filed applications for semi-fixed circuits that can operate as plural types of scramblers or descramblers (for example, Japanese Patent Laid-Open Publication No. 2005-101753). The semi-fixed circuits include a plurality of flip-flops that can be connected serially, a first selector that can select at least one signal among an exclusive OR signal of an input signal and a first feedback signal, the feedback signal, and the input signal and output a first flip-flop among the flip-flops, and a second selector that can select at least one from signal from an exclusive OR signal of an output signal from a second flip-flop among the flip-flops and a second feedback signal, the output signal from the second flip-flop, and the second feedback signal and can output the selected signal to the first selector as the first feedback signal.
However, in the conventional Viterbi decoding circuit, parameters (1) to (3) are fixed. The wireless technologies differ between, for example, the wireless LAN and the third generation mobile phone, and thus, the parameters (1) to (3) also differ. Therefore, the Viterbi decoding circuit for the wireless LAN cannot be used in the third generation mobile phone. To make a wireless device compliant with a various wireless technology types, the wireless device must have a Viterbi decoding circuit for each wireless technology.
In other words, to make a wireless device compatible with, for example, a wireless LAN based on IEEE802.11a, a wireless LAN based on IEEE802.11b, a third generation mobile phone based on a wideband code division multiple access (WCDMA), a digital broadcasting based on integrated service digital broadcasting terrestrial (ISDB-T), which is same as the wireless LAN based on IEEE802.11a, and an short-range radio based on IEEE802.15, the wireless device must have at least five types of Viterbi circuits because there are two types of WCDMA standards. This makes a size of the circuit performing the Viterbi decoding large. The size of the circuit further increases with every additional wireless technology.
Thus, the Viterbi circuit may be configured using a field programmable gate array (FPGA), which is a device in which logic components can be changed within a field. The Viterbi circuit can be made compatible with each wireless technology by changing FPGA settings. However, to change the FPGA setting information, a few hundred milliseconds are required. Assuming an application in which the wireless system is switched during voice communication, the switching of the wireless system must be completed within a few ten seconds. Therefore, the FPGA is not suitable.
Moreover, required memory capacity increases due to the large amount of information for FPGA settings, resulting in increasing the circuit area. Furthermore, it is difficult to make the FPGA settings in accordance with the desired wireless technology, unless made by an engineer familiar with the Viterbi decoding technology. In addition, the FPGA setting is complicated because the information differs with each wireless technology. Although Japanese Patent Laid-Open Publication No. 2005-101753 discloses the concept of the Viterbi decoding circuit configuration using the semi-fixed circuit, details of the configuration are not mentioned.